MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:41:36 GMT
Content-Type: text/html
Content-Length: 1645
Last-Modified: Friday, 27-Sep-96 00:34:17 GMT

<html>

<head>

<title>CS 681: Homework 3</title>

<link rev="made" href="mailto:ronitt@cs.cornell.edu">

</head>

<body BGCOLOR="#ffffff">

<h1> CS681 Homework 3</h1> September 20, 1996 <p>
<ol>
<li> 
Consider the following problem:
A town has r residents R<sub>1</sub>,...,R<sub>r</sub>; q clubs C<sub>1</sub>,...,C<sub>q</sub>;
and p political parties P<sub>1</sub>,...,P<sub>p</sub>.
Each resident is a member of at least one club and belong to exactly
one political party.  Each club must nominate
one of its members to represent it on the town's governing council so that the
number of council members belonging
to the political party P<sub>k</sub> is at most u<sub>k</sub> (for given u<sub>1</sub>,...,u<sub>p</sub>).  
It is not ok for two or more clubs to nominate the same person.
The problem is to determine whether it is possible to
find a council that satisfies this "balancing" property.
<p>

Given r, R<sub>1</sub>,...R<sub>r</sub>,q,C<sub>1</sub>,...C<sub>q</sub>,p,P<sub>1</sub>,...,P<sub>p</sub>,u<sub>1</sub>,...u<sub>p</sub>,
show how to solve this problem by solving a single max flow problem.
<p>
<li> 
You are given a graph and a max flow on the graph.  Show how to
find a minimum cut in O(m) additional time.
<p>
<li>
Show how to transform a maximum flow problem having
several source nodes and several sink nodes to one with 
only one source node and one sink node.
<p>
<li>
Construct an easy to describe family of flow 
graphs (the i<sup>th</sup> flow graph is a graph
on i nodes) with the number of cuts of minimum capacity 
growing exponentially with i.
<p>

</ol>
<p>
Due September 27 in class.


</body>

</html>


